import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Hashtable;

public class Grammar
{
	private ArrayList<Symbol> grammar;
	private ArrayList<String> tokens;
	private ArrayList<Symbol> terminals;
	private ArrayList<String> initNonTerminals;
	private Symbol start;
	private ArrayList<String> names;
	private Hashtable<Point, Rule> table;
	private ArrayList<Point> points;


	public Grammar(ArrayList<Symbol> g)
	{
		grammar = g;
		tokens = new ArrayList<String>();
		initNonTerminals = new ArrayList<String>();
		names = new ArrayList<String>();
		terminals = new ArrayList<Symbol>();
	}

	public Grammar()
	{
		tokens = new ArrayList<String>();
		initNonTerminals = new ArrayList<String>();
		names = new ArrayList<String>();	
		terminals = new ArrayList<Symbol>();
	}

	public ArrayList<Symbol> getGrammar()
	{
		return grammar;
	}

	public void setGrammar(ArrayList<Symbol> g)
	{
		grammar = g;
	}

	/**
	 * Reads a grammar in from a file using the assumed template
	 * @param filename The filename to pass in
	 */
	public void readGrammarFromFile(String filename)
	{
		if( grammar == null)
			grammar = new ArrayList<Symbol>();

		try 
		{
			BufferedReader br =  new BufferedReader(new FileReader(new File(filename)));
			try 
			{
				String line = null;
				String startName = "";
				names = new ArrayList<String>();
				int i = 0;
				while (( line = br.readLine()) != null)
				{
					switch(i)
					{
						case 0:
							String[] toks = line.substring(1).split(" ");
							for(int j = 0; j < toks.length; j++)
							{
								tokens.add(toks[j]);
								Symbol s = new Symbol(toks[j], true, toks[j]);
								terminals.add(s);

							}
							break;
						case 1:
							String[] nonTerminals = line.substring(1).split(" ");
							for(int j = 0; j < nonTerminals.length; j++)
								initNonTerminals.add(nonTerminals[j]);
							break;
						case 2:
							startName = line.substring(1);
							break;
						default:
							String name = line.substring(0,line.indexOf(':')).trim();
							String derivation = line.substring(line.indexOf(':') + 1).trim();
							String[] ders = derivation.split("\\|");
							if(names.contains(name))
							{
								for(int j = 0; j < ders.length; j++)
									grammar.get(names.indexOf(name)).
									addDerivation(ders[j].trim());
							}
							else
							{
								Symbol s = new Symbol(name, false);
								for(int j = 0; j < ders.length; j++)
									s.addDerivation(ders[j].trim());
								names.add(name);
								grammar.add(s);
								if(name.equals(startName))
									start = s;
							}
							break;
					};
					i++;
				}
			}
			finally 
			{
				br.close();
			}
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}
	
	public Hashtable<Point,Rule> getParseTable()
	{
		return table;
	}

	public ArrayList<Symbol> getTerminals()
	{
		return terminals;
	}

	public ArrayList<Point> getPoints()
	{
		return points;
	}

	public void setPoints(ArrayList<Point> points)
	{
		this.points = points;
	}

	public void setTerminals(ArrayList<Symbol> terminals)
	{
		this.terminals = terminals;
	}

	/**
	 * Removes CommonPrefix as in A : aB, A: aC
	 */
	public void removeCommonPrefix()
	{
		Symbol s;
		String aName;
		for(int i = 0; i < grammar.size(); i++)
		{
			s = grammar.get(i);
			if(!s.isTerminal())
			{
				ArrayList<String> d = s.getDerivations();
				String str;
				for(int j = 0; j < d.size()-1; j++)
				{
					for(int k = j+1; k < d.size(); k++)
					{	
						str = lcp(d.get(j), d.get(k)).trim();
						if(str.length() > 0)
						{
							aName = s.getName().substring(0,s.getName().indexOf('>'));
							while(names.contains(aName+ ">"))
								aName += "'";
							aName += ">";
							Symbol a = new Symbol(aName,false);
							a.addDerivation(d.get(j).substring(d.get(j).
									indexOf(str) + str.length()).trim());
							a.addDerivation(d.get(k).substring(d.get(j).
									indexOf(str) + str.length()).trim());

							grammar.add(a);
							names.add(aName);
							s.getDerivations().set(j, str+ " " + a.getName());
							s.getDerivations().remove(k);

						}
					}
				}
			}
		}
	}

	/**
	 * Removes left recursion from the grammar
	 */
	public void removeLeftRecursion()
	{
		removeCommonPrefix();

		Symbol s;
		String fName;
		for(int i = 0; i < grammar.size(); i++)
		{
			s = grammar.get(i);
			if(!s.isTerminal())
			{
				ArrayList<String> d = s.getDerivations();
				for(int j = 0; j < d.size(); j++)
				{
					if(d.get(j).trim().indexOf(s.getName()) == 0)
					{
						fName = s.getName().substring(0,s.getName().indexOf('>'));
						while(names.contains(fName + ">"))
							fName += "_tail";
						fName += ">";

						Symbol fixed = new Symbol(fName,false);
						fixed.addDerivation(d.get(j).trim().substring(
								s.getName().length()).trim() + " " + 
								fixed.getName());
						fixed.addDerivation("\\epsilon");

						s.getDerivations().remove(j);
						grammar.add(fixed);
						names.add(fName);
						if(s.getDerivations().size() == 0)
							s.addDerivation(fixed.getName());
						else
						{
							for(int k = 0; k < s.getDerivations().size(); k++)
							{
								s.getDerivations().set(k,
										s.getDerivations().get(k)+ " "+
										fixed.getName());
							}
						}
					}
				}
			}
		}
	}

	/**
	 * Generates the first set for all symbols
	 */
	public void generateFirstSets()
	{
		removeLeftRecursion();

		for(int k = 0; k < terminals.size(); k++)
		{
			getFirstSet(terminals.get(k));
		}

		for(int k = 0; k < grammar.size(); k++)
		{
			getFirstSet(grammar.get(k));
		}
	}

	/**
	 * Recursive helper function, per symbol
	 * @param s The symbol to get a single first set for
	 * @return The first set for a symbol
	 */
	public ArrayList<String> getFirstSet(Symbol s)
	{
		ArrayList<String> ar = new ArrayList<String>();
		if(s.isTerminal())
		{
			ar.add(s.getName());
			s.setFirstSet(ar);
			s.setFirstComplete(true);
			return s.getFirstSet();
		}
		else
		{
			if(!s.isFirstComplete())
			{
				ar = s.getDerivations();
				if(ar.size() > 0)
				{
					if(ar.contains("\\epsilon"))
					{
						s.addToFirstSet("\\epsilon");
					}
					ArrayList<Symbol> derivs;
					ArrayList<String> set = new ArrayList<String>();
					String s1;
					for(int j = 0; j < ar.size(); j++)
					{
						if(ar.get(j).equals("\\epsilon"))
							continue;
						s1 = ar.get(j);
						derivs = new ArrayList<Symbol>();

						while(s1.length() > 0)
						{
							for(int k = 0; k < grammar.size(); k++)
							{
								if(s1.trim().startsWith(grammar.get(k).getName()))
								{
									derivs.add(grammar.get(k));
									s1 = s1.substring(s1.indexOf(grammar.get(k).getName())+
											grammar.get(k).getName().length());
								}
							}

							for(int k = 0; k < terminals.size(); k++)
							{
								if(s1.trim().startsWith(terminals.get(k).getName()))
								{
									derivs.add(terminals.get(k));
									s1 = s1.substring(s1.indexOf(terminals.get(k).getName())+
											terminals.get(k).getName().length());
								}
							}
						}
						set =  getFirstSet(derivs.get(0));
						if(!set.contains("\\epsilon"))
						{
							for(int k = 0; k < set.size(); k++)
							{
								s.addToFirstSet(set.get(k));
							}
						}
						else
						{
							boolean missingEps = false;
							for(int l = 0; l < derivs.size(); l++)
							{
								if(l > 0)
								{
									set =  getFirstSet(derivs.get(l));
									missingEps = !set.contains("\\epsilon");
								}
								for(int k = 0; k < set.size(); k++)
								{
									if(set.get(k).indexOf("\\epsilon") == -1)
										s.addToFirstSet(set.get(k));
								}
							}
							if(!missingEps)
								s.addToFirstSet("\\epsilon");					

						}

					}
				}
				s.setFirstComplete(true);
			}
			return s.getFirstSet();
		}
	}

	/**
	 * Generates the follow sets for all nonTerminals
	 */
	public void generateFollowSets()
	{
		generateFirstSets();
		
		boolean loop = true;
		while(loop)
		{
			loop = false;
			for(int k = 0; k < grammar.size(); k++)
			{
				if(getFollowSet(grammar.get(k)))
					loop = true;
			}
		}
	}

	/**
	 * Iterative single-symbol helper function for generating follow sets
	 * @param s The single symbol
	 * @return true if a follow set has changed
	 */
	public boolean getFollowSet(Symbol s)
	{
		if(s.getName().equals(start.getName()))
			s.addToFollowSet("$");

		ArrayList<String> ar = s.getDerivations();
		ArrayList<Symbol> derivs;
		ArrayList<String> set = new ArrayList<String>();
		Symbol eps = new Symbol("\\epsilon", true);
		String s1;
		ArrayList<String> before = new ArrayList<String>();
		boolean anyChanges[] = null;
		ArrayList<String> after = new ArrayList<String>();

		for(int j = 0; j < ar.size(); j++)
		{
			s1 = ar.get(j);
			derivs = new ArrayList<Symbol>();

			while(s1.length() > 0)
			{
				for(int k = 0; k < grammar.size(); k++)
				{
					if(s1.trim().startsWith(grammar.get(k).getName()))
					{
						derivs.add(grammar.get(k));
						s1 = s1.substring(s1.indexOf(grammar.get(k).getName())+
								grammar.get(k).getName().length());
					}
				}

				for(int k = 0; k < terminals.size(); k++)
				{
					if(s1.trim().startsWith(terminals.get(k).getName()))
					{
						derivs.add(terminals.get(k));
						s1 = s1.substring(s1.indexOf(terminals.get(k).getName())+
								terminals.get(k).getName().length());
					}
				}

				if(s1.trim().startsWith(eps.getName()))
				{
					derivs.add(eps);
					s1 = s1.substring(s1.indexOf(eps.getName())+eps.getName().length());
				}
			}

			anyChanges = new boolean[derivs.size()];
			for(int k = 0; k < derivs.size(); k++)
			{
				for(int m = 0; m < derivs.get(k).getFollowSet().size(); m++)
					before.add(derivs.get(k).getFollowSet().get(m));

				if(!derivs.get(k).isTerminal() && !derivs.get(k).getName().equals("\\epsilon"))
				{
					if(k == derivs.size()-1)
					{
						for(int m = 0; m < s.getFollowSet().size(); m++)
						{
							derivs.get(k).addToFollowSet(s.getFollowSet().get(m));
							after = derivs.get(k).getFollowSet();
						}
						anyChanges[k] = !before.containsAll(after);
						continue;
					}
					set =  getFirstSet(derivs.get(k+1));
					if(!set.contains("\\epsilon"))
					{
						for(int l = 0; l < set.size(); l++)
						{
							for(int m = 0; m < set.size(); m++)
								derivs.get(k).addToFollowSet(set.get(m));
						}

						after = derivs.get(k).getFollowSet();
						anyChanges[k] = !before.containsAll(after);
					}
					else
					{
						boolean missingEps = false;
						ArrayList<String> dummyFirst = new ArrayList<String>();
						for(int l = k+1; l < derivs.size(); l++)
						{
							if(l > k+1)
							{
								set =  getFirstSet(derivs.get(l));
								missingEps = !set.contains("\\epsilon");
							}
							for(int m = 0; m < set.size(); m++)
							{
								if(set.get(m).indexOf("\\epsilon") == -1)
									dummyFirst.add(set.get(m));
							}
						}

						for(int m = 0; m < dummyFirst.size(); m++)
							derivs.get(k).addToFollowSet(dummyFirst.get(m));

						after = derivs.get(k).getFollowSet();
						anyChanges[k] = !before.containsAll(after);

						if(!missingEps)
						{
							for(int m = 0; m < s.getFollowSet().size(); m++)
							{
								derivs.get(k).addToFollowSet(s.getFollowSet().get(m));
								after = derivs.get(k).getFollowSet();
							}
							anyChanges[k] = !before.containsAll(after);
						}
					}

				}
			}
		}
		for(int i = 0; i < anyChanges.length; i++)
		{
			if(anyChanges[i])
				return true;
		}
		return false;
	}

	/**
	 * Prints all of the first sets for a grammar
	 */
	public void printFirstSets()
	{
		for(int k = 0; k < grammar.size(); k++)
		{
			System.out.println("First(" + 
					grammar.get(k).getName() + "): " +  
					grammar.get(k).getFirstSet());
		}
	}

	/**
	 * Prints all of the follow sets for a grammar
	 */
	public void printFollowSets()
	{
		for(int k = 0; k < grammar.size(); k++)
		{
			System.out.println("Follow(" + 
					grammar.get(k).getName() + "): " +  
					grammar.get(k).getFollowSet());
		}
	}

	/**
	 * Generates the parse table for the given grammar
	 * in the form of a hastable of Point, Rule, where Point
	 * is a helper class. Point.row corresponds to nonterminal indexes
	 * and Point.col correspondnds to terminals.
	 * 
	 * A rule is a single derivation of a Symbol
	 */
	public void generateParseTable()
	{
		generateFollowSets();
		
		table = new Hashtable<Point, Rule>();
		points = new ArrayList<Point>();
		
		ArrayList<String> ar;
		//For each Non-terminal
		for(int i = 0; i < grammar.size(); i++)
		{
			ar = grammar.get(i).getDerivations();
			//For each production rule
			if(ar.size() > 0)
			{
				ArrayList<Symbol> derivs;
				ArrayList<String> set = new ArrayList<String>();
				String s1;
				for(int j = 0; j < ar.size(); j++)
				{
					s1 = ar.get(j);
					derivs = new ArrayList<Symbol>();

					while(s1.length() > 0)
					{
						if(s1.contains("\\epsilon"))
						{
							Symbol eps = new Symbol("\\epsilon", true, "\\epsilon");
							eps.addToFirstSet("\\epsilon");
							derivs.add(eps);
							s1 = s1.substring(0,s1.indexOf("\\epsilon")) +
								s1.substring(s1.indexOf("\\epsilon") + 8);
						}
						for(int k = 0; k < grammar.size(); k++)
						{
							if(s1.trim().startsWith(grammar.get(k).getName()))
							{
								derivs.add(grammar.get(k));
								s1 = s1.substring(s1.indexOf(grammar.get(k).getName())+
										grammar.get(k).getName().length());
							}
						}

						for(int k = 0; k < terminals.size(); k++)
						{
							if(s1.trim().startsWith(terminals.get(k).getName()))
							{
								derivs.add(terminals.get(k));
								s1 = s1.substring(s1.indexOf(terminals.get(k).getName())+
										terminals.get(k).getName().length());
							}
						}
					}
					set =  derivs.get(0).getFirstSet();
					if(!set.contains("\\epsilon"))
					{
						for(int k = 0; k < set.size(); k++)
						{
							Point p = new Point(i, find(terminals, set.get(k)));
							if(find(points,p) == -1)
							{
								table.put(p, new Rule(grammar.get(i).getName(), ar.get(j)));
								points.add(p);
							}
							else
								table.put(points.get(find(points,p)), new Rule(grammar.get(i).getName(), ar.get(j)));
						}
					}
					else
					{
						boolean missingEps = false;
						for(int l = 0; l < derivs.size(); l++)
						{
							if(l > 0)
							{
								set =  derivs.get(l).getFirstSet();
								missingEps = !set.contains("\\epsilon");
							}
							for(int k = 0; k < set.size(); k++)
							{
								if(set.get(k).indexOf("\\epsilon") == -1)
								{
									Point p = new Point(i, find(terminals, set.get(k)));
									if(find(points,p) == -1)
									{
										table.put(p, new Rule(grammar.get(i).getName(), ar.get(j)));
										points.add(p);
									}
									else
										table.put(points.get(find(points,p)), new Rule(grammar.get(i).getName(), ar.get(j)));
								}
							}
						}
						if(!missingEps)
						{
							ArrayList<String> follow = grammar.get(i).getFollowSet();
							for(int k = 0; k < follow.size(); k++)
							{
								if (follow.get(k).equals("$"))
								{
									Point p = new Point(i, terminals.size());
									if(find(points,p) == -1)
									{
										table.put(p, new Rule(grammar.get(i).getName(), ar.get(j)));
										points.add(p);
									}
									else
										table.put(points.get(find(points,p)), new Rule(grammar.get(i).getName(), ar.get(j)));
								}
								else
								{
									Point p = new Point(i, find(terminals, follow.get(k)));
									if(find(points,p) == -1)
									{
										table.put(p, new Rule(grammar.get(i).getName(), ar.get(j)));
										points.add(p);
									}
									else
										table.put(points.get(find(points,p)), new Rule(grammar.get(i).getName(), ar.get(j)));
								}
							}
						}

					}

				}
			}

		}
	}
	
	public Symbol getStart()
	{
		return start;
	}

	public void setStart(Symbol start)
	{
		this.start = start;
	}

	/**
	 * Prints out a decent, but not great looking table
	 */
	public void printParseTable()
	{
		if(table != null)
		{
			System.out.print("\t");
			for(int i = 0; i < terminals.size(); i++)
			{
				System.out.print(terminals.get(i).getName() + "\t");
			}
			System.out.println("$");
			
			for(int i = 0; i < grammar.size(); i++)
			{
				System.out.print(grammar.get(i).getName() + "::\t");
				for(int j = 0; j < terminals.size()+1; j++)
				{
					Point p = new Point(i,j);
					int idx = find(points, p);
					if(idx >= 0)
						System.out.print(table.get(points.get(idx)) + "\t");
					else
						System.out.print(table.get(p) + "\t");
				}
				System.out.println();
			}
		}
	}
	
	/**
	 * Return the longest common prefix of s and t
	 * @param s A string
	 * @param t Another string
	 * @return The longest common prefix (using the symbols)
	 */
	public String lcp(String s, String t)
	{
		int n = Math.min(s.length(), t.length());
		int openIdx = 0;
		boolean closed = true;
		String ret;
		for (int i = 0; i < n; i++)
		{
			if(s.charAt(i) == '<')
			{
				openIdx = i;
				closed = false;
			}

			if (s.charAt(i) != t.charAt(i))
			{
				if(!closed)
				{
					if(i != 0)
					{
						if(s.charAt(i-1) != '>')
						{
							ret = s.substring(0, openIdx);
							while(ret.length() > 0)
							{
								for(int j = 0; j < tokens.size(); j++)
								{
									if(ret.endsWith(tokens.get(j)))
										return ret;
								}
								ret = ret.substring(0, ret.length()-1);
							}
							return ret;
						}
					}
					else
					{
						ret = s.substring(0,i);
						while(ret.length() > 0)
						{
							for(int j = 0; j < tokens.size(); j++)
							{
								if(ret.endsWith(tokens.get(j)))
									return ret;
							}
							ret = ret.substring(0, ret.length()-1);
						}
						return ret;
					}
				}
				else
				{
					ret = s.substring(0,i);
					while(ret.length() > 0)
					{
						for(int j = 0; j < tokens.size(); j++)
						{
							if(ret.endsWith(tokens.get(j)))
								return ret;
						}
						ret = ret.substring(0, ret.length()-1);
					}
					return ret;
				}
			}
			if(s.charAt(i) == '>')
				closed = true;

		}
		ret = s.substring(0, n);
		return ret;
	}
	
	/**
	 * Finds a Symbol named S in an arraylist
	 * @param a The list
	 * @param s The symbol name
	 * @return The index of s in a
	 */
	public static int find(ArrayList<Symbol> a, String s)
	{
		for(int i = 0; i < a.size(); i++)
		{
			if(a.get(i).getName().equals(s))
				return i;
		}
		return -1;
	}
	
	/**
	 * Finds a point in an arraylist
	 * @param a The arraylist
	 * @param p The point
	 * @return The index of p in a
	 */
	public static int find(ArrayList<Point> a, Point p)
	{
		for(int i = 0; i < a.size(); i++)
		{
			if(a.get(i).row == p.row && a.get(i).col == p.col)
				return i;
		}
		return -1;
	}

	/**
	 * Overrides java.lang.Object's toString method
	 */
	public String toString()
	{
		String ret = "";
		for(int i = 0; i < grammar.size(); i++)
		{
			for(int j = 0; j < grammar.get(i).getDerivations().size();j++)
			{
				ret += grammar.get(i).getName() + ": " + 
				grammar.get(i).getDerivations().get(j) + "\n"; 
			}
		}

		return ret;
	}
	
	public static void main(String[] args)
	{
		/*Symbol a = new Symbol("<a>", false);
		a.addDerivation("<a> <b>");
		a.addDerivation("<a> <c>");

		ArrayList<Symbol> c = new ArrayList<Symbol>();
		c.add(a);*/

		/*Grammar g = new Grammar();
		g.readGrammarFromFile("tiny.gram");
		g.generateFirstSets();
		g.generateFollowSets();
		//g.printFollowSets();
		g.generateParseTable();
		g.printParseTable();*/

		Grammar g1 = new Grammar();
		g1.readGrammarFromFile("book.gram");
		g1.generateFirstSets();
		g1.generateFollowSets();
		g1.generateParseTable();
		g1.printParseTable();
		
		/*Grammar g2 = new Grammar();
		g2.readGrammarFromFile("A.gram");
		g2.removeLeftRecursion();
		System.out.println(g2);*/

		/*Grammar g3 = new Grammar();
		g3.readGrammarFromFile("C.gram");
		g3.removeLeftRecursion();
		System.out.println(g3);*/

		/*Grammar g4 = new Grammar();
		g4.readGrammarFromFile("First.gram");
		g4.generateFirstSets();
		g4.generateFollowSets();
		g4.printFollowSets();*/
	}

}
